package ch6;

public class InsertSort {

	public static void main(String[] args) {
		// 插入排序
		int[] ar = { 22, 55, 6, 144, 88, 23, 77, 85, 15 };
		// 从第二个开始
		// 前面的有序
		// 找到合适的位置，采用二分法快速找到位置
		// 把合适位置上的数右移一位
		// 空出来的位置就是当前数的位置
		// 当前数，暂存
		for (int i = 1; i < ar.length; i++) {
			int low = 0, high = i - 1;
			int mid;
			int temp = ar[i];
			// 从大到小
			while (low <= high) {
				mid = (low + high) / 2;
				if (ar[mid] < temp)
					high = mid - 1;
				else
					low = mid + 1;
			}
			// low就是合适的位置
			// 从low到i-1位置上的数，移动到low+1到i
			for (int k = i - 1; k >= low; k--) {
				ar[k + 1] = ar[k];
			}
			ar[low] = temp;
		}
		System.out.println("排序后：");
		for (int i : ar)
			System.out.print(i + " \t");
	}

}
